Lớp NP-đầy đủ là tập hợp các bài toán NP-khó trong NP.

Lớp NP-đầy đủ được quan tâm nghiên cứu bởi khả năng kiểm chứng nhanh chóng lời giải (NP) dường như có liên hệ với khả năng tìm kiếm nhanh chóng lời giải (P). Hiện vẫn chưa biết được nếu mọi bài toán trong NP đều có thể được giải quyết nhanh chóng hay không (đây chính là bài toán P so với NP). Tuy nhiên, nếu bất kì một bài toán nào trong NP-đầy đủ có thể được giải quyết nhanh chóng, thì theo định nghĩa của NP-đầy đủ, mọi bài toán trong NP đều có thể được giải quyết nhanh chóng.